//Given an n x n matrix where each of the rows and columns are sorted in ascendi
//ng order, return the kth smallest element in the matrix. 
//
// Note that it is the kth smallest element in the sorted order, not the kth dis
//tinct element. 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
//Output: 13
//Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the
// 8th smallest number is 13
// 
//
// Example 2: 
//
// 
//Input: matrix = [[-5]], k = 1
//Output: -5
// 
//
// 
// Constraints: 
//
// 
// n == matrix.length 
// n == matrix[i].length 
// 1 <= n <= 300 
// -109 <= matrix[i][j] <= 109 
// All the rows and columns of matrix are guaranteed to be sorted in non-decreas
//ing order. 
// 1 <= k <= n2 
// 
// Related Topics 堆 二分查找 
// 👍 584 👎 0


package leetcode.editor.cn;

import java.util.Comparator;
import java.util.PriorityQueue;

//Java：Kth Smallest Element in a Sorted Matrix
class P378KthSmallestElementInASortedMatrix {
    public static void main(String[] args) {
        Solution solution = new P378KthSmallestElementInASortedMatrix().new Solution();
        // TO TEST
        System.out.println(solution.kthSmallestMerge(new int[][]
                {{1, 5, 9},
                        {10, 11, 13},
                        {12, 13, 15}}, 6));
        System.out.println(solution.kthSmallestDivide(new int[][]
                {{1, 5, 9},
                        {10, 11, 13},
                        {12, 13, 15}}, 6));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.通过堆
        public int kthSmallest(int[][] matrix, int k) {
            if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
                return 0;
            }
            int row = matrix.length - 1;
            int col = matrix[0].length - 1;
            if ((row + 1) * (col + 1) <= k) {
                return matrix[row][col];
            }
            if (k == 1) {
                return matrix[0][0];
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i <= row; i++) {
                for (int j = 0; j <= col; j++) {
                    int val = matrix[i][j];
                    if (queue.size() >= k) {
                        if (queue.peek() > val) {
                            queue.poll();
                            queue.offer(val);
                        }
                    } else {
                        queue.offer(val);
                    }
                }
            }
            return queue.peek();
        }
        //2.归并算法
        public int kthSmallestMerge(int[][] matrix, int k) {
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return a[0] - b[0];
                }
            });
            int n = matrix.length;
            for (int i = 0; i < n; i++) {
                pq.offer(new int[]{matrix[i][0], i, 0});
            }
            for (int i = 0; i < k - 1; i++) {
                int[] now = pq.poll();
                if (now[2] != n - 1) {
                    pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
                }
            }
            return pq.poll()[0];
        }
        //3.二分查找
        public int kthSmallestDivide(int[][] matrix, int k) {
            int n = matrix.length;
            int left = matrix[0][0];
            int right = matrix[n - 1][n - 1];
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (check(matrix, mid, k, n)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        public boolean check(int[][] matrix, int mid, int k, int n) {
            int i = n - 1;
            int j = 0;
            int num = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] <= mid) {
                    num += i + 1;
                    j++;
                } else {
                    i--;
                }
            }
            return num >= k;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}